package com.giteelou.simple;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 简单公式计算器，但计算的结合性是有问题的，因为它使用了如下语法规则：
 * additive -> multiplicative | multiplicative + additive
 * multiplicative -> primary | primary * multiplicative
 * 其递归项在右边，会自然的对应右结合。我们真正需要的是左结合。
 */
public class SimpleCalculator {

    public static void main(String[] args) {

        SimpleLexer lexer = new SimpleLexer();

        String statement = "int a = 2 + 3 * 5;";
        List<Token> tokens = lexer.analyze(statement);

        lexer.print();

        Queue<Token> tokenQueue = new LinkedList<>(tokens);

        SimpleCalculator calculator = new SimpleCalculator();

        try {
            System.out.println("语句: " + statement + "\n语法分析结果:");
            ASTNode node = calculator.intDeclare(tokenQueue);
            calculator.dumpAST(node, "|-");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        System.out.println("-------------");

        statement = "2 + 3 * 5"; // 正常
        calculator.evaluate(statement);

        statement = "2+"; // 语法错误
        calculator.evaluate(statement);

        statement = "2+3+4"; // 结合性有问题
        calculator.evaluate(statement);
    }

    /**
     * 计算算术表达式
     *
     * @param statement 表达式
     */
    public void evaluate(String statement) {
        System.out.println("公式: " + statement + "\n语法分析和计算过程及结果:");
        List<Token> tokens = new SimpleLexer().analyze(statement);
        Queue<Token> tokenQueue = new LinkedList<>(tokens);
        try {
            SimpleASTNode node = additive(tokenQueue);
            evaluate(node, "|-");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        System.out.println("-------------");
    }

    /**
     * 计算算数表达式
     *
     * @param node   AST node
     * @param indent 缩进
     * @return 计算结果
     */
    private int evaluate(ASTNode node, String indent) {
        int result = 0;
        ASTNodeType type = node.getType();
        System.out.println(indent + node.getType() + " " + node.getText());
        switch (type) {
            case AdditiveExp:
                ASTNode child1 = node.getChildren().get(0);
                ASTNode child2 = node.getChildren().get(1);
                result = evaluate(child1, "| " + indent)
                        + evaluate(child2, "| " + indent);
                break;
            case MultiplicativeExp:
                child1 = node.getChildren().get(0);
                child2 = node.getChildren().get(1);
                result = evaluate(child1, "| " + indent)
                        * evaluate(child2, "| " + indent);
                break;
            case IntLiteral:
                result = Integer.parseInt(node.getText());
                break;
        }
        System.out.println(indent + "result: " + result);
        return result;
    }

    /**
     * 打印抽象语法树(abstract syntax tree)
     *
     * @param node   node
     * @param indent 缩进字符
     */
    public void dumpAST(ASTNode node, String indent) {
        System.out.println(indent + node.getType() + " " + node.getText());
        for (ASTNode child : node.getChildren()) {
            dumpAST(child, "| " + indent);
        }
    }

    /**
     * 解析int变量声明语句语法
     *
     * @param tokenQueue token队列
     * @return AST树
     */
    public SimpleASTNode intDeclare(Queue<Token> tokenQueue) throws Exception {
        SimpleASTNode node = null;
        Token token = tokenQueue.peek(); // 预读
        if (token != null && token.getType() == TokenType.Int) { // 是int关键字
            tokenQueue.poll(); // 消费掉int
            token = tokenQueue.peek();
            if (token != null && token.getType() == TokenType.Identifier) { // 是标识符（变量名）
                node = new SimpleASTNode(ASTNodeType.Program, token.getText());
                tokenQueue.poll(); // 消费掉标识符
                token = tokenQueue.peek();
                if (token != null && token.getType() == TokenType.Assignment) { // 是赋值符号
                    tokenQueue.poll(); // 消费掉赋值符号
                    SimpleASTNode child = additive(tokenQueue); // 匹配一个表达式
                    if (child == null) {
                        throw new Exception("invalid variable initialization, expecting an expression");
                    }
                    node.addChild(child);
                }
            } else {
                throw new Exception("variable name expected");
            }

            token = tokenQueue.peek();
            if (token != null && token.getType() == TokenType.Semicolon) {
                tokenQueue.poll();
            } else {
                throw new Exception("invalid statement, expecting semicolon");
            }
        }
        return node;
    }

    /**
     * 分析加法表达式
     * 比如: 2 + 3 * 5
     * additive -> multiplicative | multiplicative + additive
     * multiplicative -> primary | primary * multiplicative
     *
     * @param tokenQueue token queue
     * @return node
     */
    private SimpleASTNode additive(Queue<Token> tokenQueue) throws Exception {
        SimpleASTNode child1 = multiplicative(tokenQueue);
        SimpleASTNode node = child1;
        Token token = tokenQueue.peek();
        if (child1 != null && token != null) {
            if (token.getType() == TokenType.Plus) {
                tokenQueue.poll();
                SimpleASTNode child2 = additive(tokenQueue);
                if (child2 != null) {
                    node = new SimpleASTNode(ASTNodeType.AdditiveExp, token.getText());
                    node.addChild(child1);
                    node.addChild(child2);
                } else {
                    throw new Exception("invalid additive expression, expecting the right part.");
                }
            }
        }

        return node;
    }

    /**
     * 分析乘法表达式
     *
     * @param tokenQueue token queue
     * @return node
     */
    private SimpleASTNode multiplicative(Queue<Token> tokenQueue) throws Exception {
        SimpleASTNode child1 = primary(tokenQueue);
        SimpleASTNode node = child1;
        Token token = tokenQueue.peek();
        if (child1 != null && token != null) {
            if (token.getType() == TokenType.Star) {
                tokenQueue.poll();
                SimpleASTNode child2 = multiplicative(tokenQueue);
                if (child2 != null) {
                    node = new SimpleASTNode(ASTNodeType.MultiplicativeExp, token.getText());
                    node.addChild(child1);
                    node.addChild(child2);
                } else {
                    throw new Exception("invalid multiplicative expression, expecting the right part.");
                }
            }
        }

        return node;
    }

    /**
     * 分析基础表达式
     *
     * @param tokenQueue token queue
     * @return node
     */
    private SimpleASTNode primary(Queue<Token> tokenQueue) throws Exception {
        SimpleASTNode node = null;
        Token token = tokenQueue.peek();
        if (token != null) {
            if (token.getType() == TokenType.IntLiteral) {
                tokenQueue.poll();
                node = new SimpleASTNode(ASTNodeType.IntLiteral, token.getText());
            } else if (token.getType() == TokenType.Identifier) {
                tokenQueue.poll();
                node = new SimpleASTNode(ASTNodeType.Identifier, token.getText());
            } else if (token.getType() == TokenType.LeftParenthesis) {
                tokenQueue.poll();
                node = additive(tokenQueue);
                if (node != null) {
                    token = tokenQueue.peek();
                    if (token != null && token.getType() == TokenType.RightParenthesis) {
                        tokenQueue.poll();
                    } else {
                        throw new Exception("expecting right parenthesis");
                    }
                } else {
                    throw new Exception("expecting an additive expression inside parenthesis");
                }
            }
        }
        return node;
    }


    /**
     * ASTNode的简单实现。
     */
    private static class SimpleASTNode implements ASTNode {

        private final ASTNodeType type;
        private final String text;
        private SimpleASTNode parent;
        private final List<ASTNode> children;

        SimpleASTNode(ASTNodeType type, String text) {
            this.type = type;
            this.text = text;
            children = new ArrayList<>();
        }

        public void addChild(SimpleASTNode child) {
            children.add(child);
            child.parent = this;
        }

        @Override
        public ASTNodeType getType() {
            return type;
        }

        @Override
        public String getText() {
            return text;
        }

        @Override
        public ASTNode getParent() {
            return parent;
        }

        @Override
        public List<ASTNode> getChildren() {
            return children;
        }
    }
}
